\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\textbf{problem：}

\begin{itemize}
\item
  给定 \(M\) 个约束条件，问满足这 \(M\) 个约束条件的长度为 \(N\)
  排列有多少个\\
  每个约束条件为一个三元组 \((x , y, z)\)，要求 \(a_1,a_2,..,a_x\) 小于
  \(y\) 的数的个数不超过 \(z\)
\end{itemize}

\textbf{solve}

可以将 \(x\) 位置的约束条件存储在 \(vec[x]\) 中，并定义 \(dp[i][bit]\)
表示：

\begin{itemize}
\item
  用 \(bit\) 这个状态对应的数（这些数都得用上）
\item
  组成长度为 \(i\) 的排列的方案数
\item
  （这些排列需要满足 \(vec[1]\) \textasciitilde{} \(vec[i]\)
  的约束条件）
\end{itemize}

那么答案就为 \(dp[n][(1 << n) - 1]\)

\begin{itemize}
\item
  而如果 \(bit\) 这个状态对应的数的个数等于 \(i\)
\item
  这 \(i\) 个数满足 \(vec[i]\) 的约束条件
\end{itemize}

那么可得：\(if(bit >> k \& 1) dp[i][bit] += dp[i - 1][bit - (1 << k)];\)\\
然后考虑一波优化：\\
先定义 \(cnt(bit)\) 表示 \(bit\) 这个状态对应的数的个数。\\
上面有个 \(dp\) 的转移条件是 ：

\begin{itemize}
\item
  \(bit\) 这个状态对应的数的个数等于 \(i\)，
\end{itemize}

也就是说只有当 \(i = cnt[bit]\) 时才能进行转移（只有
\(dp[cnt(bit)][bit]\) 是有效的）\\
那么只要枚举 \(bit\)，就可以得到对应有效的 \(i\) (\(i = cnt(bit)\))\\
于是我们可以去掉 \(dp\) 数组的一维，并去掉一层循环\\
即定义 \(dp[bit]\) 表示：

\begin{itemize}
\item
  用 \(bit\) 这个状态对应的数（这些数都得用上）
\item
  组成长度为 \(cnt[bit(i)]\) 的排列的方案数
\item
  （这些排列需要满足 \(vec[1]\) \textasciitilde{} \(vec[cnt(bit)]\)
  的约束条件）
\end{itemize}

最后答案为 \(dp[(1 << n) - 1]\)，转移方程类似

\begin{lstlisting}
int get(int x)
{
	int res = 0;
	while(x)
	{
		if(x & 1) res ++ ;	
		x >>= 1;
	}
	return res;
}
vector<pair<int , int>>vec[19];
long long dp[1 << 18];
int cnt[1 << 18];
signed main()
{
	int n , m , x , y , z;
	cin >> n >> m;
	for(int i = 1 ; i <= m ; i ++)
	{
		cin >> x >> y >> z;
		vec[x].push_back(make_pair(y , z));
	}
	for(int bit = 1 ; bit < (1 << n) ; bit ++) cnt[bit] = get(bit);
	dp[0] = 1;
	for(int bit = 0 ; bit < (1 << n) ; bit ++)
	{
		vector<int>num;	
		for(int k = 0 ; k < n ; k ++)
		{
			if(bit >> k & 1) num.push_back(k + 1);
		}
		int flag = 0;
		for(auto q : vec[cnt[bit]])
		{
			int y = q.first , z = q.second , sum = 0;
			for(auto h : num)
			{
				if(h <= y) sum ++ ;
			}	
			if(sum > z) { flag = 1 ; break ; }
		}	
		if(flag) continue ;	
		for(auto k : num) dp[bit] += dp[bit - (1 << (k - 1))];
	} 
	cout << dp[(1 << n) - 1] << '\n';
	return 0;
}
\end{lstlisting}

\end{document}
